//------------------------------------------------------------------------------
// X2D Game Engine
// Copyright (C) 2006-2007 Janusz Kowalski
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.
//------------------------------------------------------------------------------

// RawVector is something like std::vector, but:
// - RawVector shrinks, when elements are removed.
// - RawVector doesn't call copy-constructors when it moves it's content.

#include <cstdlib>
#include <cstring>
#include <new>

#ifndef RAW_VECTOR_H
#define RAW_VECTOR_H

//-----------------------------------------------------------------------------
// RawVector
//-----------------------------------------------------------------------------

// This vector uses realloc() from the Standard C Library. Objects are moved
// without calling their copy-constructors, so please be carefull.

// !! Algorithm calculating the next-highest power of 2 may be not the best
// example of a portable code.

template <class T> class RawVector {
  private:
    T *data_;
    unsigned size_;
  public:
    RawVector();
    RawVector(const RawVector &src);
    RawVector& operator=(const RawVector& right);
    
    void add(const T &item);
    void add(T &item);
    inline T& operator[] (unsigned i) const;
    void removeElementAt(unsigned i);
    inline unsigned size() const {return size_;}
    bool removeElement(const T& elem);
    //int indexOf(const T& elem);
    // Returns index of element, or invalid index (i >= size()).
    unsigned indexOf__(const T& elem);
    void insertElementAt(const T& elem, int i);
    ~RawVector();
    T& lastElement();
    void clear();
};

template <class T> RawVector<T>::RawVector() : data_(0), size_(0) { }

template <class T> RawVector<T>::RawVector(const RawVector &src) {
  unsigned n = src.size_;
  
  // Find next-highest power of 2.
  n=n-1; n=n|(n>>1); n=n|(n>>2); n=n|(n>>4);
  if(sizeof(n)>1) n=n|(n>>8); if(sizeof(n)>2) n=n|(n>>16);
  n++;
  
  // Allocate space.
  if(n>0) {
    data_ = static_cast<T*>(malloc(sizeof(T)*n));
    if(data_==0) {
      size_=0;
      throw "RawVector: Copy: ERROR: malloc failed!";
    }
  } else data_=0;
  
  // Copy data.
  size_=src.size_;
  memcpy(data_, src.data_, sizeof(T)*size_);
}

template <class T> RawVector<T>& RawVector<T>::operator=(const RawVector& right) {
  // Check for self-assignment.
  if(this==&right) return *this;
  
  // Calculate how much space do we need (next highest power of two).
  unsigned n = right.size_;
  n=n-1; n=n|(n>>1); n=n|(n>>2); n=n|(n>>4);
  if(sizeof(n)>1) n=n|(n>>8); if(sizeof(n)>2) n=n|(n>>16);
  n++;
  
  if(n>0) {
    T* tmp = static_cast<T*>(malloc(sizeof(T)*n));
    if(tmp!=0) {
      // Call destructors.
      clear();
      data_=tmp;
    } else throw "RawVector: Assignment operator: ERROR: malloc failed.";
  } else free(data_);
  
  size_ = right.size_;
  memcpy(data_, right.data_, sizeof(T)*size_);
  return *this;
}

template <class T> void RawVector<T>::add(const T &item) {
  // If size_ is a power of 2 or 0 (0,1,2,4,8,16,etc.)
  if((size_&(size_-1))==0) {
    T* tmp = static_cast<T*>(realloc(data_, sizeof(T)*(size_>0?2*size_:1)));
    if(tmp!=0) data_=tmp;
    else throw "RawVector::add(): ERROR: realloc failed!";
  }
  new (data_+size_) T(item);
  //data_[size_]=item;
  size_++;
}

template <class T> void RawVector<T>::add(T &item) {
  // If size_ is a power of 2 or 0 (0,1,2,4,8,16,etc.)
  if((size_&(size_-1))==0) {
    T* tmp = static_cast<T*>(realloc(data_, sizeof(T)*(size_>0?2*size_:1)));
    if(tmp!=0) data_=tmp;
    else throw "RawVector::add(): ERROR: realloc failed!";
  }
  new (data_+size_) T(item);
  //data_[size_]=item;
  size_++;
}

template <class T> void RawVector<T>::insertElementAt(const T& elem, int i) {
  // If size_ is a power of 2 or 0 (0,1,2,4,8,16,etc.)
  if((size_&(size_-1))==0) {
    T* tmp = static_cast<T*>(realloc(data_, sizeof(T)*(size_>0?2*size_:1)));
    if(tmp!=0) data_=tmp;
    else throw "RawVector::add(): ERROR: realloc failed!";
  }
  //for(int k = size_+1; k>i; k--) data_[k]=data_[k-1];
  memmove(data_+i+1, data_+i, sizeof(T)*(size_-i));
  new (data_+i) T(elem);
  //data_[i]=elem;
  size_++;
}

template <class T> T& RawVector<T>::operator[] (unsigned i) const {
  return data_[i];
}

template <class T> void RawVector<T>::removeElementAt(unsigned i) {
  // Call destructor of the removed object.
  data_[i].~T();
  memmove(data_+i, data_+i+1, sizeof(T)*(size_-i-1));
  size_--;
  if((size_&(size_-1))==0) {
    T* tmp = static_cast<T*>(realloc(data_, sizeof(T)*size_));
    if((tmp!=0)||(size_==0)) data_=tmp;
    else throw "RawVector::removeElementAt(): ERROR: realloc failed!";
  }
}

template <class T> RawVector<T>::~RawVector() {
  clear();
}

template <class T> unsigned RawVector<T>::indexOf__(const T& elem) {
  for(unsigned i=0; i<size_; i++)
    if(data_[i]==elem) return i;
  return size();
}

template <class T> bool RawVector<T>::removeElement(const T& elem) {
  for(unsigned i=0; i<size_; i++)
    if(data_[i]==elem) {
      removeElementAt(i);
      return true;
    }
  return false;
}

template <class T> T& RawVector<T>::lastElement() {
  if(size_>0) return data_[size_-1];
  else throw "RawVector: ERROR: No such element!";
}


template <class T> void RawVector<T>::clear() {
  for(unsigned i=0; i<size_; i++) data_[i].~T();
  free(data_); data_=0; size_=0;
};

template <class T> class LPtr;
template <class T> class LPtrMaster;

//------------------------------------------------------------------------------
// Linked pointer
//------------------------------------------------------------------------------

template <class T> class LPtr {
  friend class LPtrMaster<T>;
  protected:
    T *ptr_;
    // This one is public for flexibility.
    void set(T* ptr) { ptr_=ptr; }
  private:
    mutable LPtr<T> *next_;
    mutable LPtr<T> *prev_;
    void release() {
      if(next_!=this) {
        next_->prev_=prev_;
        prev_->next_=next_;
      }
      ptr_=0;
    }
    void acquire(const LPtr<T> &lptr) {
      ptr_=lptr.ptr_;
      next_=lptr.next_;
      prev_=lptr.next_->prev_; // Nice trick.
      lptr.next_->prev_=this;
      lptr.next_=this;
    }
  public:
    LPtr(T *ptr) : ptr_(ptr), next_(this), prev_(this) { }
    LPtr() : ptr_(0), next_(this), prev_(this) { }
    LPtr(const LPtr<T> &lptr) {
      acquire(lptr);
    }
    
    ~LPtr() {
      release();
    }
    bool isNull() const throw() { return ptr_==0; }
    T& operator*() const throw() { return *ptr_; }
    T* operator->() const throw() { return ptr_; }
    LPtr<T> *next() const throw() { return next_; }
    LPtr<T> *prev() const throw() { return prev_; }
    LPtr<T> &operator= (const LPtr<T> &lptr) {
      if(this!=&lptr) {
        release();
        acquire(lptr);
      }
      return *this;
    }
    void nullify()  {
      LPtr<T> *lptr = this;
      do {
        lptr->set(0); lptr=lptr->next();
      } while (lptr!=this);
    }
};

//------------------------------------------------------------------------------
// Master linked pointer
//------------------------------------------------------------------------------

// This is a special kind of linked pointer, that zeroes all the other pointers
// in the list when destroyed.

template <class T> class LPtrMaster : public LPtr<T> {
  public:
    LPtrMaster (T* ptr) : LPtr<T>(ptr) { }
    ~LPtrMaster() {
      // This is required according to the C++ standard.
      void nullify();
      nullify();
    }
};

//------------------------------------------------------------------------------
// Ptr - Smart pointer
//------------------------------------------------------------------------------

template <class T> class Ptr {
  private:
    T *ptr_;
  public:
    Ptr(T* ptr = 0) : ptr_(ptr) { }
    ~Ptr() {delete ptr_;}
    Ptr(Ptr<T> &src) {ptr_=src.ptr_; src.ptr_=0;}
    Ptr<T> &operator=(Ptr<T>& right) {ptr_=right.ptr_; right.ptr_=0;}
    T& operator*() {return *ptr_;}
    T* operator->() {return ptr_;}
};

//------------------------------------------------------------------------------
// APtr - Smart pointer to array
//------------------------------------------------------------------------------
// APtr object may be stored in RawVector.

template <class T> class APtr {
  private:
    T* ptr_;
  public:
    APtr(T* ptr = 0) : ptr_(ptr) { }
    ~APtr() {delete[] ptr_;}
    T& operator[](unsigned i) {return ptr_[i];}
    APtr(APtr<T>& src) {
      ptr_=src.ptr_; src.ptr_=0;
    }
    APtr<T>& operator=(APtr<T>& right) {
      ptr_=right.ptr_; delete[] right.ptr_;
    }
    bool isNull() {return (ptr_==0?true:false);}
};

//------------------------------------------------------------------------------
// Reference
//------------------------------------------------------------------------------
// !! Objects of this class cannot be stored in RawVector.
class Ref {
  protected:
    Ref *next_;
    Ref *prev_;
    void *ptr_;
    Ref(void *ptr = 0) : ptr_(ptr) {
      next_=this; prev_=this;
    }
    void join(Ref &ref) {
      ref.next_->prev_ = this; next_=ref.next_;
      ref.next_ = this; prev_=&ref;
    }
    void leave() {
      prev_->next_ = next_; next_->prev_=prev_;
    }
};

// Array reference.
template <class T> class ARef : private Ref {
  public:
    ARef(T* ptr=0) : Ref(ptr) { }
    ARef(ARef<T> &src) { join(src); }
    ~ARef() {
      if(next_==this) delete[] static_cast<T*>(ptr_);
      else leave();
    }
    T& operator[](unsigned i) {
      return static_cast<T*>(ptr_)[i];
    }
    ARef<T>& operator=(ARef<T>& right) {
      leave(); join(right);
    }
};

#endif
